#include <stdio.h>

/*
    堆的结构一般用完全二叉树的结构来访问，存储的话可以用树结构和数组，使用数组的话节省空间，使用二叉树的话会浪费空间
    时间复杂度 NlogN
    时间复杂度的logN 指的是 以2为底的对数

*/



void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}


// 大堆序 用来升序
void heapify_big(int *arr, int size,int idx)
{
    int min_idx = idx;
    while(1)
    {
        if ((2*idx+1) < size && arr[2*idx+1] > arr[idx])
        {
            min_idx = 2*idx+1;
        }

        if ((2*idx+2) < size && arr[2*idx+2] > arr[min_idx])
        {
            min_idx = 2*idx+2;
        }

        if (min_idx == idx)
        {
            break;
        }

        swap(&arr[min_idx],&arr[idx]);
        // 继续处理下面的节点，从交换后的节点继续往下堆化
        idx = min_idx;
    }
}

// 小堆序，用来降序排列
void heapify_small(int *arr, int size,int idx)
{
    int min_idx = idx;
    while(1)
    {
        if ((2*idx+1) < size && arr[2*idx+1] < arr[idx])
        {
            min_idx = 2*idx+1;
        }

        if ((2*idx+2) < size && arr[2*idx+2] < arr[min_idx])
        {
            min_idx = 2*idx+2;
        }

        if (min_idx == idx)
        {
            break;
        }

        swap(&arr[min_idx],&arr[idx]);
        // 继续处理下面的节点，从交换后的节点继续往下堆化
        idx = min_idx;
    }
}

// big heap sort
void buildheap(int *arr,int size)
{
    // 从最后一个非叶子节点开始建堆
    for (int i = size/2-1;i >= 0;i--)
    {
        heapify(arr,size,i);
        // 一轮堆化后的打印
        // printf("heapsort array: [");
        // for (int i = 0;i < size;i++)
        // {
        //     printf(" %d ",arr[i]);
        // }
        // printf("]\n");
        // printf("********\n");
    }

    
    
}



void heapsort(int *arr,int size)
{

    buildheap(arr,size);

    for (int i = size-1;i >= 0;i--)
    {
        swap(&arr[i],&arr[0]);
        heapify(arr,i,0);
    }

}




int main (int argc, char *argv[])
{

    #define SIZE 6

    int array[SIZE] = {4,6,8,2,9,2};

    heapsort(array,SIZE);

    printf("heapsort array: [");
    for (int i = 0;i < SIZE;i++)
    {
        printf(" %d ",array[i]);
    }
    printf("]\n");



    return 0;
}